package com.chao.sort;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 归并排序
 * @date : 2023/7/10
 */
public class MergeSort {

    public static void main(String[] args) {
        int []arr = new int[] {5,0,3,8,3,4,52,32,26,19,36};
        arr = sort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));;
    }

    private static int[] sort(int[] arr,int left,int right) {
        if (left >= right) {
            return arr;
        }
        int mid = (left + right) / 2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        return merge(arr,left,mid,right);
    }

    private static int[] merge(int []arr,int left,int mid,int right) {
        int[] newArr = new int[right - left + 1];
        int i = left,j = mid + 1,k = 0,p=0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                newArr[k++] = arr[i++];
            } else {
                newArr[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            newArr[k++] = arr[i++];
        }

        while (j<= right) {
            newArr[k++] = arr[j++];
        }

        while (left<=right) {
            arr[left++] = newArr[p++];
        }
        return newArr;
    }
}
